/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    struct Compare {
        bool operator()(const pair<ListNode*, int>& p1,
                        const pair<ListNode*, int>& p2) {
            return p1.second > p2.second;
        }
    };
    ListNode* sortList(ListNode* head) {
        if (head == nullptr)
            return nullptr;
        priority_queue<pair<ListNode*, int>, vector<pair<ListNode*, int>>,
                       Compare>
            q;
        ListNode* cur = head;
        while (cur) {
            q.push({cur, cur->val});
            cur = cur->next;
        }
        head = q.top().first;
        cur = head;
        while (!q.empty()) {
            ListNode* top = q.top().first;
            q.pop();
            cur->next = top;
            cur = top;
        }
        cur->next = nullptr;
        return head;
    }
};